package com.mamingchao.basic.swardToOffer.one;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;

public class FindDuplicateNum {


    public static void main(String[] args) {
        int[] param = {2, 3, 1, 0, 2, 5, 3,9,8,7,6,3,4,3,9};
        String result1 = getDuplicateNums(param);
        System.out.println(result1);

        int[] param1 = {3,9,2,5,7};
        int[] target = getHashMapArray(param1);
        System.out.println(Arrays.toString(target));


        int [] preorder = {3,9,20,15,7}, inorder = {9,3,15,20,7};

        int maxBTreeSize = getMaxBinaryTreeElementCount(preorder.length);

        System.out.println("二叉树对应的完全二叉树的元素数量 -》" + maxBTreeSize);


        List<String> cengxuArray = new ArrayList<>();
        caculateThreeNodeBTree(cengxuArray, preorder, inorder);


        String result = Arrays.toString(cengxuArray.toArray());

        ListIterator<String> temp = cengxuArray.listIterator();

        System.out.println(result);
        if (temp.hasNext()) {
            System.out.println(temp.next() + ",");
        }

    }





    /**
     *
     * @param nums 输入原始整形数组 [2, 3, 1, 0, 2, 5, 3]
     * @return 输出重复的数字，和重复的次数；比如，数组成员2，2次；数组成员3，2次；
     */
    private static String getDuplicateNums(int[] nums) {
        int length = nums.length;

        int[] temp = new int[length];

        for (int i = 0; i < length; i++) {
            temp[nums[i]] += 1;
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] > 1) {
                sb.append("数组成员");
                sb.append(i);
                sb.append(",");
                sb.append(temp[i]);
                sb.append("次");
                sb.append("; \n");
            }
        }

        return sb.toString();
    }


    /**
     *
     * @param cengxuArray 输出的二叉树层序 序列数组
     * @param needToCaculatePreArray
     * @param needToCaculateMidArray
     */
    private static void caculateThreeNodeBTree(List<String> cengxuArray, int[] needToCaculatePreArray, int[] needToCaculateMidArray) {
        if (needToCaculatePreArray.length < 1) {
            cengxuArray.add("null");
            return;
        }
        // 获取根节点
        int rootValue = needToCaculatePreArray[0];
        cengxuArray.add(String.valueOf(rootValue));

        // 获取 中序 队列的 value 哈希映射 index数组
        int[] midHashMapArray = getHashMapArray(needToCaculateMidArray);

        // 获得 根节点在 中序序列中的index值
        int indexOfRootInMidArray = midHashMapArray[rootValue];

        // 获得 中序序列 从0 - 根节点的子数组；即根节点左侧的子数组
        int[] leftOfPreArray = Arrays.copyOfRange(needToCaculatePreArray,1 , indexOfRootInMidArray + 1);
        // 获得 中序序列 从0 - 根节点的子数组；即根节点右侧的子数组
        int[] rightOfPreArray = Arrays.copyOfRange(needToCaculatePreArray,indexOfRootInMidArray + 1 , needToCaculatePreArray.length);


        // 获得 中序序列 从0 - 根节点的子数组；即根节点左侧的子数组
        int[] leftOfMidArray = Arrays.copyOfRange(needToCaculateMidArray,0 , indexOfRootInMidArray);
        // 获得 中序序列 从0 - 根节点的子数组；即根节点左侧的子数组
        int[] rightOfMidArray = Arrays.copyOfRange(needToCaculateMidArray,indexOfRootInMidArray + 1 , needToCaculateMidArray.length);

        // 递归执行 左侧
        caculateThreeNodeBTree(cengxuArray, leftOfPreArray,leftOfMidArray);
        // 递归执行右侧
        caculateThreeNodeBTree(cengxuArray, rightOfPreArray,rightOfMidArray);

    }

    /**
     * 根据 整型数组，获取 source数组value 对应 target数组 index，target数组 value对应 source数组的index的
     * 哈希映射数组
     * 示例：source 数组 [3,9,2,5,7]
     * 输出 [0,0,2,0,0,3,0,4,0,1]
     * 如果像找5在原数组的index位置，直接 target[5] = 3
     * @param source
     * @return
     */
    private static int[] getHashMapArray(int[] source) {
        // target 数组的初始值 为source 数组的长度
        int length = source.length;

        // 计算target 数组的长度；以source的 最大值 + 1
        for (int i = 0; i < source.length; i++) {
            if (source[i] > length) {
                length = source[i];
            }
        }

        int[] target = new int[length + 1];

        for (int i = 0; i < source.length; i++) {
            target[source[i]] = i;
        }

        return target;
    }





    /**
     * 根据前序或者中序的 二叉树数组数量，算出 二叉树的层高，和 如果该树是完全二叉树，
     * 节点的数量
     * @return
     */
    private static int getMaxBinaryTreeElementCount(int preOrderElementArrSize) {
        int level =  (int)Math.ceil(Math.log(preOrderElementArrSize)/Math.log(2));
        return level;
    }


    private static void testMaxBinaryTreeElementCount() {
        for (int i = 2; i < 100; i++) {
            System.out.println("输入的值为-》" + i);
            System.out.println(Math.ceil(Math.log(i)/Math.log(2)));
            System.out.println((int)(Math.log(i)/Math.log(2)));
            System.out.println();
        }
    }
}
